1. Field of the Invention
The present invention relates to a program control apparatus and a memory allocation apparatus. More specifically, the present invention relates to a program control apparatus and a memory allocation apparatus ensuring execution of a process exclusively and ensures real time operation, without using computer resources for lock mechanism such as a semaphore and an event flag.
Definitions of various terms used in the specification of the present invention are as follows.
(1) Process
A virtual address space containing one or more threads.
(2) Thread
The basic unit of program execution. A process can have several threads running concurrently, each performing a different job, such as waiting for events or performing a time-consuming job that the program doesn't need to complete before going on. When a thread has finished its job, the thread is suspended or destroyed.
(3) Context
(In relation to object oriented system) an object storing information necessary for executing a method. The contexts consists of a context of a call destination, a method object containing a program, a program counter, information referred to as a stack pointer, an area for taking an argument or temporary variable, and an evaluation stack. Such environment of execution is used as the object. The context is referred to as heap language indicating the feature of high level language supporting the process and the like. In PASCAL or ALGOL 60, such environment of execution is provided in the stack, while in FORTRAN, the environment of execution is provided in a fixed area.
(4) Task
In an environment of multi-programming or multi-processing, one or more trains of instructions handled by a control program as an element of a job to be executed by the computer.
(5) Garbage
An object created but not referenced. Collected by garbage collection.
(6) Garbage Collection
The automatic detection and freeing of memory that is no longer in use. The Java runtime system performs garbage collection section so that programmers never explicitly free objects.
(7) Interpreter
A module that alternately decodes and executes every statement in some body of code. The Java interpreter decodes and executes bytecode for the Java virtual machine.
(8) Real Time
A term representing a system in which processing of data input to the system is performed substantially at the same time as the event.
(9) Object
An entity for coupling a procedure with data characteristic, based on which calculation is performed and local state is stored.
(10) Class
In the Java programming language, a type that defines the implementation of a particular kind of object. A class definition defines instance and class variables and methods, as well as specifying the interfaces the class implements and the immediate superclass of the class. If the superclass is not explicitly specified, the superclass will implicitly be object.
(11) Heap Area
Work area of the memory used as needed while a program is being executed.
(12) Scheduling
Selecting a job or a task to be dispatched.
(13) Event
A change in the state of hardware/software noticed to other hardware/software. Generally in this notice, various parameters representing the type of event and the state of hardware/software are transmitted together as a message to the receiver. The receiver receiving the event notice performs an appropriate process in accordance with the message parameters and the like.
(14) Event Flag
Task-to-task synchronous communication mechanism where the task has a function of waiting for an occurrence of one or a plurality of events and a function of noticing the event.
(15) Semaphore
In a system processing a plurality of processes or tasks concurrently, a scheme for realizing synchronization between processes or tasks, message control and interruption.
(16) Virtual Machine
An environment for executing an application program not dependent on a specific platform, incorporated in a plurality of specific platforms (OS or hardware). When the same virtual machine is provided, the same application program can be executed even when platforms differ.
(17) Java VM (Java Virtual Machine)
The part of the Java runtime environment responsible for interpreting bytecodes.
(18) Free Area
A usable area on the heap area.
A not-yet used area.
(19) Normal Thread
A thread performing a process not requiring real time operation.
(20) Mark Table
A table used to see if an object is referenced or not, with each element of the table being in one to one correspondence to the object. When it is confirmed that an object has a reference, a column of the table corresponding to the object is marked. After all reference relations are confirmed, objects left unmarked are unnecessary, and therefore these objects can be deleted.
(21) Life Time of Object
The time from creation to deletion of an object.
(22) Write Barrier
Checking of a change in reference relation to an object and performing some process when there is an overwrite. In the present specification, when there is an overwrite, a column of the mark table corresponding to that object which is referenced is marked.
(23) Sweeping
A process of deleting an unnecessary object on the heap area.
(24) Create the Object
Allocating a part of the heap area to an object and to initialize contents of the object.
(25) Delete the Object
Removing an unnecessary object. More specifically, an area secured on the heap area is freed.
(26) Reference
For an object A to access another object B, necessary information specifying object B. More specifically, a pointer or an index indicating object B.
(27) Change the Reference/Reconnected the Reference
Change of reference from a present object B to another object C.
2. Description of the Background Art
Consider concurrent processing of a plurality of threads on an operating system, in a computer system having a single processor. Here, for mutual exclusion using a shared memory, and for synchronization with among a plurality of tasks, mutual exclusion is controlled by using a semaphore or an event flag.
Further, in order to operate a program in an environment of a small memory capacity, a so called dynamic memory management has been utilized, in which a memory of a single address space is dynamically allocated when a program is executed, without utilizing a virtual memory. In such dynamic memory management, use of a once allocated memory area often ceases. In such situation, unless the memory area is explicitly freed by the program, the memory area cannot be re-used. As a result, the program gradually runs short of available free area. In order to avoid such a problem, a process referred to as garbage collection (hereinafter referred to as “GC”) is performed. GC extracts wasted or no longer used memory areas (garbage), collects these memory areas and provide the resulting area as a re-usable flee area.
FIG. 1 shows, in the form of a flow chart, the process steps of conventional GC. Various methods such as mark & sweep method, copy method and reference count method have been proposed as GC algorithms. Here, mark & sweep method will be described as an example. Referring to FIG. 1, in order to prevent any thread other than the GC thread from being executed during GC, interruption of other threads is inhibited, and operation mode enters single thread mode (s201). Thereafter, mark storing areas (hereinafter referred to as “mark table”) respectively corresponding to objects allocated to an area as an object of GC on the memory (hereinafter referred to as “heap area”) are cleared (s202). Thereafter, based on information representing reference relation of objects allocated to the heap area, objects which are referenced by any other object are detected, and corresponding positions on the mark table are marked (s203). An object which is not referenced by any other object is a wasted object which is not used any longer. In this process, that position of the mark table which corresponds to the non-referenced object is not marked. Therefore, an area to which the object which is not marked is allocated is extracted as an area to which a new object is allocatable, that is, as a free area (s204). The free area is generated as data in the form of a list, for example. Thereafter, interruption inhibition is cancelled, and the operation mode returns to a multi thread mode (s205).
Conventionally, such GC is automatically activated when the free area of the memory is decreased to a prescribed amount.
By GC, objects of various different sizes (memory sizes) are freed, resulting in fragmentation in the heap area. In order to secure a continuous large sized areas, memory compaction (hereinafter simply referred to as “compaction”) is performed in which object allocation areas are successively packed starting from the head.
In the conventional system, the function of mutual exclusion described above is implemented by utilizing computer resources such as a semaphore or an event flag. Therefore, when the resource is used by a certain thread, other thread have to wait until the resource is freed and available. The time for waiting causes a great hindrance in a system requiring real time response. More specifically, the thread which is waiting for the resource cannot be processed until the resource is freed. Therefore, real time response of the threads is impossible.
According to the above described conventional GC, the wider the memory space, the longer it takes to find areas which can be collected as garbage. For example, it takes few seconds for a heap area of 64 to 128 MB. Further, GC is performed irregularly when the free area is decreased to some extent. For this reason, GC cannot be used in a system requiring real time response.
In the system requiring a real time response, when an event (interruption) occurs while a task is being executed, another thread corresponding to the event will be processed. Here, the time necessary for switching of the thread need to be at most several tens μsec, for example, in the worst case. In the conventional method, however, activation of GC is unpredictable, as described above, and once activated, CPU (Central Processing Unit) operates only for GC for few seconds. In this period, real time processing is impossible.
This problem is caused not only by GC, and the problem is commonly experienced in systems which suffer from long period of wait time for resources.
As another method of GC, a method of ensuring real time operation by incrementally performing the conventional copy method has been described in JYOUHOUSHORI (Information Processing) Vol. 35 No. 11 pp. 1008˜1010. Here, “incremental” means that even when a process is interrupted, the process can be started from the interrupted portion when resumed. This method allows interruption of the process amid GC. Therefore, concurrent processing of GC time-divisionally with other threads is possible in a sense. In this method of incremental execution of the copy method, however, the memory cannot be used by other thread during copying. This means that concurrent processing of only a few threads which do not use the memory is possible. Further, in the copy method, both the memory area for the source and destination of the original and the copy must be secured. This degrades efficiency of use of the memory, and therefore the method is not suitable for a system which is operated in an environment of a small memory capacity.
The method of marking every time a reference relation is changed or reconnected in order that the mark & sweep method corresponds to multi threads is referred to as “on-the-fly GC.” A method for multi CPU implementation in which a process is allocated to a CPU used only for GC is described in JYOUHOUSHORI Vol. 35 No. 11 pp. 1006˜1008. In this method, however, when objects are continuously created and reference relation is reconnected, it becomes necessary to go over and over an already marked tree to search for a new node and to mark the newly found node. This may results in endless marking or very long time for marking. Further, this method requires locking of the system during sweeping.
Further, conventional GC in accordance with mark & sweep method or the like involves compaction for eliminating fragmentation of the heap area. The CPU consumes considerable power for compaction, whereas without compaction, efficiency in use of the memory is much degraded.
Further, in a conventional object oriented system, objects having a long life and existing permanently and objects having a short life which cease in a short time exist mixtedly on the heap area. Accordingly, when GC is performed, objects having shorter lives are deleted first, resulting in fragmentation in the memory area, and therefore efficiency in use of the memory degrades abruptly. In GC, determination as to whether an object is a garbage or not must be made every time even on a permanently existing object. This wastes the power of the CPU. In order to solve this problem, so called generation garbage collection has been proposed, in which objects which have existed for a prescribed time period are considered permanent and excluded from the search for presence. Even this method, however, has a disadvantage that unnecessary objects still exist, or it is necessary to check and see existence of objects at every prescribed period.
The incremental GC by mark & sweep method will be described with reference to FIG. 2 to 47.
Referring to FIG. 2, the overall process procedure of GC in accordance with mark & sweep method will be described with reference to FIG. 2. In the GC, clearing of the mark table, marking by tree searching described above and deletion (sweep) of an object are repeated.
Referring to FIG. 3, the content of “mark clear” process of FIG. 2 will be described. In this process, contents of the mark table are cleared temporarily. First, a pointer is moved to the head of the mark table (s131), a mark at the position pointed by the pointer is cleared (s132), and the pointer is moved to a next mark position (s133). Such steps are repeated for all marks (s134→s132→ . . . ).
Referring to FIG. 4, the contents of the process “deletion of object” in FIG. 40 will be described with reference to FIG. 4. First, the pointer is moved to the head of the mark table (s141). Whether there is a mark or not is detected and if not marked, a position in the heap area of an object corresponding to that position which is pointed by the pointer on the mark table is calculated, and the corresponding object is deleted (s142→s143→s144). Thereafter, the pointer of the mark table is moved to a next position and similar steps are repeated (s145→s146→s142→ . . . ). In this manner, objects which are marked on the mark table are left while other objects are deleted from the heap area.
Next, marking in the mark & sweep method will be described.
Referring to FIGS. 5A to 5C, the procedure of marking through tree searching will be described. As can be seen in FIG. 5A, reference relation represented by the tree structure is traced from a root node 10 to each node, and a node (object) which has a reference relation is marked. More specifically, a bit at a corresponding position of the mark table is set. The tree structure is constituted by contents of variables provided in the object indicating, for example, what object references what other object, and tracing of the reference relation of the objects corresponds to tracing of the tree.
Referring to FIG. 5A, assume that there is an interruption at a time point when nodes up to node 3 have been marked. By the interruption, reference relation from root node 10 to an object represented by node 7 is disconnected as shown in FIG. 5B, and a new reference relation is generated in which an object represented by node 2 references an object represented by node 7. When the interruption process is terminated, the flow returns to the GC thread and marking is restarted, the reference relation from the root node to be object represented by node 7 is lost. Therefore, referring to FIG. 5, the pointer returns to root node 10 and thereafter proceeds to node 8 which has the reference relation. At this time point, nodes 5 and 6 are not marked. Therefore, it is necessary for an object of which reference relation is changed or reconnected to trace the tree starting from that object and mark any object which is referenced by that object.
Referring to FIG. 6, the process of “object creation” will be described. First, a kernel locks the system (s151). A free area in the heap area is searched for (s152). A necessary size is allocated to an area larger than the size of an object to be created (s153→s154). A mark is marked (write barrier) indicating that there is a reference reconnection (s155), and the system is unlocked (s156).
Referring to FIG. 7, the process of “marking indicating reference reconnection” will be described. First, based on the reference reconnected object, a position on the mark table is calculated, and whether or not corresponding mark is WHITE determined. The WHITE mark is represented by 2 bits of 00, for example, representing unmarked state. If corresponding mark is not a WHITE mark, it means that the position is already marked, and the process is terminated. If the mark is the WHITE mark, it is marked GRAY. The GRAY mark is represented by 2 bits of 01, for example, indicating that the object has been subjected to reference reconnection. The calculation for finding the mark position from the object may be performed by multiplying the address of the object by ⅛ and adding an offset, or performed based on a serial number of the object.
Referring to FIG. 8, the process of “marking through tree search” will be described. First, a pointer for tracing the tree is moved to the root node of the tree (s161), and a newly created object is marked BLACK (s162). Thereafter, tracing the tree, the pointer is moved to a next object (s163), and the steps are repeated until the end of the tree (s164→s162→ . . .). Thereafter, the pointer is moved to the head of each thread stack (a stack generated for each thread) (s165), and an objects in the stack is marked by a corresponding mark (s166). Thereafter, the pointer is moved to the next object of the stack (s167), and the steps are repeated until the end of the tree (s168→s166→ . . . ). Thereafter, the pointer is moved to the next thread stack (s169), and similar steps are repeated until the end of the thread stack (s170→s166→ . . . ). The process steps for the thread stack are performed for every thread stack (s171→s172→s165→ . . . ). In this series of tree search, if any GRAY mark is detected, searching and marking are performed again starting from the root node (s173→s161→ . . . ).
Referring to FIG. 9, the process of “corresponding marking of object”will be described. In this process, based on a created object, a position on the mark table is calculated, and the position is marked BLACK. The BLACK mark is represented by 2 bits of 1x, for example, indicating that the object is in a marked state. Here, x represents 0 or 1.
According to the method of marking in the incremental GC by mark & sweep method, when there is an interruption amid the process and reference relation between objects is changed, GRAY mark is marked, and therefore tree search must be repeated. It is possible that marking never ends, and thus GC is kept pending endlessly.